#include <iostream>
#include <cstdlib>
#include <ctime>

template<typename T>

class BinaryTree
{
private:
    class Node
    {
    public:
    T data;
    Node* lc;
    Node* rc;
    Node* parent;
    Node(T _data);
    };
    Node* root;
    void inorder_walk(Node* _x) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node* predecessor(Node* _x) const;
    Node* min(Node* _x) const;
    Node* max(Node* _x) const;

public:
    BinaryTree() {root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    Node* tree_search(T _data);
    void inorder_walk() const;
    void test_successor();
    void test_predecessor();
    void test_min_and_max();
};

template<typename T>
void inorder_treewalk(T* _arr, int n)
{
    BinaryTree<T> B;
    for(int i = 1; i < n; i++)
    {
        srand((unsigned)time(NULL));
        int k = rand()%(n-i+1);
        B.insert(_arr[k]);
        _arr[k] = _arr[n - i];
    }
    B.insert(_arr[0]);
    B.inorder_walk();
};

template<typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
    root = p;
};

template<typename T>
void BinaryTree<T>::release(Node* _x)
{
    if(_x != NULL)
    {
        release(_x->lc);
        release(_x->rc);
        delete _x;
    }
};

template<typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template<typename T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template<typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    while (x != NULL)
    {
        y = x;
        if(p->data < y->data)
            x = x->lc;
        else
            x = x->rc;
    }
    p->parent = y;
    if (y == NULL)
    root = p;
    else if (p->data < y->data)
    y->lc = p;
    else
    y->rc = p;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::tree_search(T _data)
{
    Node* x = root;
    while(x != NULL && x->data != _data)
    {
        if(_data < x->data)
        x = x->lc;
        else
        x = x->rc;
    }
    if( x == NULL)
    {
        std::cout << "Not Found" << std::endl;
        return NULL;
    }
    else
    {
        return x;
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
        inorder_walk(_x->lc);
        std::cout << _x->data << "\t";
        inorder_walk(_x->rc);
    }
};

template<typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while(_x->lc != NULL)
    {
        _x = _x->lc;
    }
    return _x;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
    while(_x->rc != NULL)
    {
        _x = _x->rc;
    }
    return _x;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
    return min(x->rc);
    Node* y = _x->parent;
    while(y != NULL && x == y->rc)
    {
        x = y;
        y = x->parent;
    }
    return y;
};

template<typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
    Node* x = _x;
    if (x->lc != NULL)
    return max(x->lc);
    Node* y = _x->parent;
    while(y != NULL && x == y->lc)
    {
        x = y;
        y = x->parent;
    }
    return y;
};

template<typename T>
void BinaryTree<T>::test_min_and_max()
{
    std::cout << "min: " << min(root)->data << "\t" << "max: " << max(root)->data << std::endl;
};

template<typename T>
void BinaryTree<T>::test_successor()
{
    std::cout << "successor: " << successor(root->lc)->data << std::endl;
};

template<typename T>
void BinaryTree<T>::test_predecessor()
{
    std::cout << "predecessor: " << predecessor(root->lc)->data << std::endl;
};
